/**
 * king
 */
package cn.scau.info.chao;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * @author king
 *
 */
public class AntColonyOptimization {

	// n个城市的坐标
	private List<Coordinate> cities;
	//
	private int antNumber = 10;
	// 最大迭代次数
	private int NC_MAX = 100;
	// 表征信息素重要程度的参数
	private double alpha;
	// 表征启发式因子重要程度的参数
	private double beta;
	// 信息素蒸发系数
	private double rho;
	// 信息素增加强度系数
	private double q;

	// 很小的值
	private double smallNumber = 0.00001;
	// 启发因子，这里设为距离的倒数
	private double[][] eta;
	// 信息素矩阵
	private double[][] tau;
	// 存储并记录路径的生成
	private int[][] tabu;

	// 各代最佳路线
	private int[][] route_best;
	// 各代最佳路线的长度
	private double[] len_best;
	// 各代路线的平均长度
	private double[] len_ave;

	/**
	 * @param cities
	 * @param ant_number
	 * @param nC_MAX
	 * @param alpha
	 * @param beta
	 * @param rho
	 * @param q
	 */
	public AntColonyOptimization(List<Coordinate> cities, int antNumber,
			int nC_MAX, double alpha, double beta, double rho, double q,
			int type, int chooseCityType) {
		super();
		this.cities = cities;
		this.antNumber = antNumber;
		NC_MAX = nC_MAX;
		this.alpha = alpha;
		this.beta = beta;
		this.rho = rho;
		this.q = q;

		// 第一步：变量初始化
		// 城市个数
		int citiesNumber = cities.size();
		// 完全图的赋权邻接矩阵
		double[][] weightedAdjacencyMatrix = new double[citiesNumber][citiesNumber];
		// 启发因子，这里设为距离的倒数
		eta = new double[citiesNumber][citiesNumber];
		// 信息素矩阵
		tau = new double[citiesNumber][citiesNumber];
		// 存储并记录路径的生成
		tabu = new int[antNumber][citiesNumber];

		for (int i = 0; i < weightedAdjacencyMatrix.length; i++) {
			for (int j = 0; j < weightedAdjacencyMatrix[i].length; j++) {
				if (i == j) {
					weightedAdjacencyMatrix[i][j] = smallNumber;
					continue;
				} else {
					weightedAdjacencyMatrix[i][j] = Coordinate.getDistance(
							cities.get(i), cities.get(j));
				}
				weightedAdjacencyMatrix[j][i] = weightedAdjacencyMatrix[i][j];

			}
		}

		for (int i = 0; i < weightedAdjacencyMatrix.length; i++) {
			for (int j = 0; j < weightedAdjacencyMatrix[i].length; j++) {
				eta[i][j] = 1 / weightedAdjacencyMatrix[i][j];
				tau[i][j] = 1;
			}
		}

		int NC = 1;
		route_best = new int[NC_MAX][citiesNumber];
		len_best = new double[NC_MAX];
		for (int i = 0; i < len_best.length; i++) {
			len_best[i] = Double.POSITIVE_INFINITY;
		}
		len_ave = new double[NC_MAX];

		// 开始迭代 停止条件之一：达到最大迭代次数，停止
		while (NC <= NC_MAX) {
			// 随意将antNumber只蚂蚁放到citiesNumber个城市上
			List<Integer> integers = new ArrayList<Integer>();
			for (int i = 0; i <= Math.ceil(antNumber / citiesNumber); i++) {
				LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
				randomSet(0, citiesNumber, citiesNumber, set);
				for (Iterator iterator = set.iterator(); iterator.hasNext();) {
					Integer integer = (Integer) iterator.next();
					integers.add(integer);
				}
			}

			for (int i = 0; i < tabu.length; i++) {
				tabu[i][0] = integers.get(i);
			}

			// antNumber只蚂蚁按概率函数选择下一座城市，完成周游
			for (int i = 1; i < citiesNumber; i++) {// 城市
				for (int j = 0; j < antNumber; j++) {// 蚂蚁
					// for (int j2 = 0; j2 < tabu.length; j2++) {
					// for (int k = 0; k < tabu[j2].length; k++) {
					// System.out.print(tabu[j2][k]+" ");
					// }
					// System.out.println();
					// }
					// 记录已经走过的城市
					List<Integer> visitedCities = new ArrayList<Integer>();
					for (int k = 0; k < i; k++) {
						visitedCities.add(tabu[j][k]);
					}
					// 剩下未走的城市
					int[] unvisitedCities = new int[citiesNumber - i];
					for (int k = 0, v = 0; k < citiesNumber; k++) {
						// System.out.println(NC+" "+i+" "+k+" "+v+" "+unvisitedCities.length+" "+visitedCities.size());
						// System.out.println(visitedCities);
						if (!visitedCities.contains(k)) {
							unvisitedCities[v] = k;
							v++;
						}
					}

					// 待访问城市的选择概率分布
					double[] p = new double[citiesNumber - i];
					double sumP = 0;
					for (int k = 0; k < p.length; k++) {
						p[k] = Math
								.pow(tau[visitedCities
										.get(visitedCities.size() - 1)][k],
										alpha)
								* Math.pow(eta[visitedCities.get(visitedCities
										.size() - 1)][k], beta);
						sumP += p[k];
					}

					Map<Double, Integer> map = new TreeMap<Double, Integer>();

					for (int k = 0; k < p.length; k++) {
						p[k] = p[k] / sumP;
						map.put(p[k], k);
					}

					double temp = 0;
					int toVisit = 0;
					// 按概率原则选取下一个城市(直接选择最大的)
					// for (int k = 0; k < p.length; k++) {
					// if (temp <= p[k]) {
					// temp = p[k];
					// toVisit = k;
					// }
					// }
					// 按概率原则选取下一个城市(选择较大的)
					int num = chooseCityType;// 前几个
					int rand = (int) (Math.random() * num);
					int count = 0;
					for (Entry<Double, Integer> entry : map.entrySet()) {
						if (rand == count) {
							temp = entry.getKey();
							toVisit = entry.getValue();
							break;
						}
						count++;
						// System.out.println("Key = " + entry.getKey() +
						// ", Value = " + entry.getValue());

					}

					tabu[j][i] = unvisitedCities[toVisit];
				}
			}

			// 记录本次迭代最佳路线
			// 开始距离为0，antNumber的列向量
			double[] lens = new double[antNumber];
			for (int i = 0; i < antNumber; i++) {
				// 每只蚂蚁的路径
				int[] route = tabu[i];
				for (int j = 0; j < citiesNumber - 1; j++) {
					lens[i] = lens[i]
							+ weightedAdjacencyMatrix[route[j]][route[j + 1]];
				}
				// 一轮下来后走过的距离
				lens[i] = lens[i]
						+ weightedAdjacencyMatrix[route[0]][route[citiesNumber - 1]];
			}

			// 选择最小距离
			double temp = Double.POSITIVE_INFINITY;
			int bestIndex = 0;
			for (int k = 0; k < lens.length; k++) {
				if (temp > lens[k]) {
					temp = lens[k];
					bestIndex = k;
				}
			}

			len_best[NC - 1] = temp;
			route_best[NC - 1] = tabu[bestIndex];
			len_ave[NC - 1] = 0;
			for (int i = 0; i < antNumber; i++) {
				len_ave[NC - 1] = len_ave[NC - 1] + lens[i];
			}
			len_ave[NC - 1] = len_ave[NC - 1] / antNumber;

			// 迭代继续
			NC++;

			// 更新信息素
			double[][] deltaTau = null;
			if (type == 0) {
				deltaTau = getACSDeltaTau(citiesNumber, lens);
			} else if (type == 1) {
				deltaTau = getAQSDeltaTau(citiesNumber, lens,
						weightedAdjacencyMatrix);
			} else if (type == 2) {
				deltaTau = getADSDeltaTau(citiesNumber);
			}
			// for (int i = 0; i < deltaTau.length; i++) {
			// for (int j = 0; j < deltaTau[i].length; j++) {
			// System.out.print(deltaTau[i][j] + " ");
			// }
			// System.out.println();
			// }
			// 考虑信息素挥发，更新后的信息素
			for (int i = 0; i < tau.length; i++) {
				for (int j = 0; j < tau[i].length; j++) {
					tau[i][j] = (1 - rho) * tau[i][j] + deltaTau[i][j];
				}
			}

			// 路径记录表清零
			tabu = new int[antNumber][citiesNumber];
		}
		// for (int i = 0; i < tau.length; i++) {
		// for (int j = 0; j < tau.length; j++) {
		// System.out.print(tau[i][j]+" ");
		// }
		// System.out.println();
		// }
		// 输出结果
		// 选择最小距离
		double temp = Double.POSITIVE_INFINITY;
		int bestIndex = 0;
		for (int i = 0; i < len_best.length; i++) {
			// System.out.println("len_best[i]: " + len_best[i]);
			if (temp > len_best[i]) {
				temp = len_best[i];
				bestIndex = i;
			}
		}
		System.out.println("min: " + temp);
		int[] route = route_best[bestIndex];
		for (int i = 0; i < route.length; i++) {
			System.out.print(route[i] + " ");
		}

		int width = 800;
		int height = 700;
		int len = 600;
		int step = 20;
		int tickX = (width - len) / 2;
		int tickY = (height + len) / 2;

		// 显示界面
		DrawAxis test = new DrawAxis();
		// 由外部用户给出参数
		Axis axisX = new Axis();
		axisX.setTickX(tickX);
		axisX.setTickY(tickY);
		axisX.setTickLength(len);
		axisX.setTickStep(step);

		axisX.setCoordinates(cities);

		List<Line> lines = new ArrayList<Line>();

		for (int i = 0; i < route.length - 1; i++) {
			Coordinate a = cities.get(route[i]);
			Coordinate b = cities.get(route[i + 1]);
			Line line = new Line(a, b);

			lines.add(line);
		}

		Coordinate a = cities.get(route[route.length - 1]);
		Coordinate b = cities.get(route[0]);
		Line line = new Line(a, b);

		lines.add(line);
		test.setText("最优解路径长度： " + temp);
		axisX.setLines(lines);
		test.setAxis(axisX);

		test.setTitle("蚂蚁算法");
		test.setSize(width, height);
		test.setLocationRelativeTo(null);
		test.setVisible(true);
	}

	/**
	 * 随机指定范围内N个不重复的数 利用HashSet的特征，只能存放不同的值
	 * 
	 * @param min
	 *            指定范围最小值
	 * @param max
	 *            指定范围最大值
	 * @param n
	 *            随机数个数
	 * @param HashSet
	 *            <Integer> set 随机数结果集
	 */
	public static void randomSet(int min, int max, int n,
			LinkedHashSet<Integer> set) {
		if (n > (max - min + 1) || max < min) {
			return;
		}
		for (int i = 0; i < n; i++) {
			// 调用Math.random()方法
			int num = (int) (Math.random() * (max - min)) + min;
			set.add(num);// 将不同的数存入HashSet中
		}
		int setSize = set.size();
		// 如果存入的数小于指定生成的个数，则调用递归再生成剩余个数的随机数，如此循环，直到达到指定大小
		if (setSize < n) {
			randomSet(min, max, n, set);// 递归
		}
	}

	/**
	 * ant-desity system
	 * 
	 * @param citiesNumber
	 * @param lens
	 * @return double[][]
	 */
	private double[][] getADSDeltaTau(int citiesNumber) {
		double[][] deltaTau = new double[citiesNumber][citiesNumber];
		for (int i = 0; i < antNumber; i++) {
			// t为第i只蚂蚁在路径（i，j）上的留下的信息量
			// lens[i]为第i只蚂蚁在环游一周的路径长度
			double t = q;

			for (int j = 0; j < citiesNumber - 1; j++) {
				// 此次循环在路径（i，j）上的信息素增量
				deltaTau[tabu[i][j]][tabu[i][j + 1]] = deltaTau[tabu[i][j]][tabu[i][j + 1]]
						+ t;
			}
			// 此次循环在整个路径上的信息素增量
			deltaTau[tabu[i][citiesNumber - 1]][tabu[i][0]] = deltaTau[tabu[i][citiesNumber - 1]][tabu[i][0]]
					+ t;
		}
		return deltaTau;
	}

	/**
	 * ant-quantity system
	 * 
	 * @param citiesNumber
	 * @param lens
	 * @return double[][]
	 */
	private double[][] getAQSDeltaTau(int citiesNumber, double[] lens,
			double[][] weightedAdjacencyMatrix) {
		double[][] deltaTau = new double[citiesNumber][citiesNumber];
		for (int i = 0; i < antNumber; i++) {
			for (int j = 0; j < citiesNumber - 1; j++) {
				// t为第i只蚂蚁在路径（i，j）上的留下的信息量
				// ant-quantity system lens[i]为第i只蚂蚁在环游一周的路径长度
				double t = q / weightedAdjacencyMatrix[j][j + 1];
				// 此次循环在路径（i，j）上的信息素增量
				deltaTau[tabu[i][j]][tabu[i][j + 1]] = deltaTau[tabu[i][j]][tabu[i][j + 1]]
						+ t;
			}
			// t为第i只蚂蚁在路径（i，j）上的留下的信息量
			// ant-quantity system lens[i]为第i只蚂蚁在环游一周的路径长度
			double t = q / weightedAdjacencyMatrix[citiesNumber - 1][0];
			// 此次循环在整个路径上的信息素增量
			deltaTau[tabu[i][citiesNumber - 1]][tabu[i][0]] = deltaTau[tabu[i][citiesNumber - 1]][tabu[i][0]]
					+ t;
		}
		return deltaTau;
	}

	/**
	 * ant-cycle system
	 * 
	 * @param citiesNumber
	 * @param lens
	 * @return double[][]
	 */
	private double[][] getACSDeltaTau(int citiesNumber, double[] lens) {
		double[][] deltaTau = new double[citiesNumber][citiesNumber];
		for (int i = 0; i < antNumber; i++) {
			// t为第i只蚂蚁在路径（i，j）上的留下的信息量
			// lens[i]为第i只蚂蚁在环游一周的路径长度
			double t = q / lens[i];
			// System.out.println(t+" ");
			for (int j = 0; j < citiesNumber - 1; j++) {
				// 此次循环在路径（i，j）上的信息素增量
				deltaTau[tabu[i][j]][tabu[i][j + 1]] = deltaTau[tabu[i][j]][tabu[i][j + 1]]
						+ t;
			}
			// 此次循环在整个路径上的信息素增量
			deltaTau[tabu[i][citiesNumber - 1]][tabu[i][0]] = deltaTau[tabu[i][citiesNumber - 1]][tabu[i][0]]
					+ t;
		}
		return deltaTau;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<Coordinate> cities = new ArrayList<Coordinate>();
		cities.add(new Coordinate(10, 10));
		cities.add(new Coordinate(25, 25));
		cities.add(new Coordinate(20, 20));
		cities.add(new Coordinate(10, 20));
		cities.add(new Coordinate(20, 10));
		cities.add(new Coordinate(15, 15));
		AntColonyOptimization aco = new AntColonyOptimization(cities, 50, 100,
				1.f, 5f, 0.5f, 1f, 0, 2);
	}

	/**
	 * @return the cities
	 */
	public List<Coordinate> getCities() {
		return cities;
	}

	/**
	 * @param cities
	 *            the cities to set
	 */
	public void setCities(List<Coordinate> cities) {
		this.cities = cities;
	}

	/**
	 * @return the antNumber
	 */
	public int getAntNumber() {
		return antNumber;
	}

	/**
	 * @param antNumber
	 *            the antNumber to set
	 */
	public void setAntNumber(int antNumber) {
		this.antNumber = antNumber;
	}

	/**
	 * @return the nC_MAX
	 */
	public int getNC_MAX() {
		return NC_MAX;
	}

	/**
	 * @param nC_MAX
	 *            the nC_MAX to set
	 */
	public void setNC_MAX(int nC_MAX) {
		NC_MAX = nC_MAX;
	}

	/**
	 * @return the alpha
	 */
	public double getAlpha() {
		return alpha;
	}

	/**
	 * @param alpha
	 *            the alpha to set
	 */
	public void setAlpha(double alpha) {
		this.alpha = alpha;
	}

	/**
	 * @return the beta
	 */
	public double getBeta() {
		return beta;
	}

	/**
	 * @param beta
	 *            the beta to set
	 */
	public void setBeta(double beta) {
		this.beta = beta;
	}

	/**
	 * @return the rho
	 */
	public double getRho() {
		return rho;
	}

	/**
	 * @param rho
	 *            the rho to set
	 */
	public void setRho(double rho) {
		this.rho = rho;
	}

	/**
	 * @return the q
	 */
	public double getQ() {
		return q;
	}

	/**
	 * @param q
	 *            the q to set
	 */
	public void setQ(double q) {
		this.q = q;
	}

	/**
	 * @return the eta
	 */
	public double[][] getEta() {
		return eta;
	}

	/**
	 * @param eta
	 *            the eta to set
	 */
	public void setEta(double[][] eta) {
		this.eta = eta;
	}

	/**
	 * @return the len_best
	 */
	public double[] getLen_best() {
		return len_best;
	}

	/**
	 * @param len_best
	 *            the len_best to set
	 */
	public void setLen_best(double[] len_best) {
		this.len_best = len_best;
	}

	/**
	 * @return the len_ave
	 */
	public double[] getLen_ave() {
		return len_ave;
	}

	/**
	 * @param len_ave
	 *            the len_ave to set
	 */
	public void setLen_ave(double[] len_ave) {
		this.len_ave = len_ave;
	}
}
